/**
 * https://leetcode.cn/problems/count-number-of-ways-to-place-houses/submissions/566873447/
 * 2320. 统计放置房子的方式数
 * medium 2024.09.22
 * 多维dp
 */

class Solution {
public:
    typedef long long ll;
    const ll mod=1e9+7;
    int countHousePlacements(int n) {
        vector<int>dp(n+2,0);
        dp[1]=2;
        dp[2]=3;
        for(int i=3;i<=n;i++)
            dp[i]=((dp[i-1]%mod)+(dp[i-2]%mod))%mod;
        return ((dp[n]%mod)*(dp[n]%mod))%mod;
    }
};